package codeRandomThoughts.Test337打家劫舍III;

import codeRandomThoughts.utils.TreeNode;

public class Solution2 {
    public int rob(TreeNode root) {
        return postOrder(root)[0];
    }

    /**
     * @param root 入口
     * @return res[0]:当前节点的最高金额 res[1]:当前节点左右子树的最高金额
     */
    public int[] postOrder(TreeNode root) {
        //遍历到叶子节点
        if (root.left == null && root.right == null) {
            //当前节点的最高金额为当前房屋的价值
            //当前节点没有左右子树,所以当前节点左右子树的最高金额为0
            return new int[]{root.val, 0};
        }

        //遍历左子树
        int[] left = new int[2];
        if (root.left != null) {
            left = postOrder(root.left);
        }

        //遍历右子树
        int[] right = new int[2];
        if (root.right != null) {
            right = postOrder(root.right);
        }

        //设定根节点的值
        int[] res = new int[2];
        //当前节点的最高金额可以分为两种情况:
        //1.当前节点不偷,偷左右子树 left[0]+right[0]
        //2.当前节点偷,左右子树不偷,偷左右子树的孩子 left[1]+right[1]+root.val
        res[0] = Math.max(left[0] + right[0], left[1] + right[1] + root.val);

        //当前节点左右子树的最高金额,就是把左子树的最高金额加上右子树的最高金额
        res[1] = left[0] + right[0];
        return res;
    }
}
